package easy

import (
	. "GoLeetcode/common"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 一棵树A是另一棵树B的子树，存在以下三种情况
// 1.两棵树相等
// 2.A是B的左子树的子树
// 3.A是B的右子树的子树
// 1带2递归法: 先用一个辅助方法处理现有节点,然后用题目给出的方法作为已有功能使用,进行左右子树的递归
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
	if root == nil && subRoot == nil {
		return true
	}
	if root == nil && subRoot != nil {
		return false
	}
	// 这里isSameTree可能会由于root和subRoot其中一个为nil而另一个不为nil而返回false
	// 所以需要在这之前对root为nil的情况进行处理
	return isSameTree(root, subRoot) ||
		isSubtree(root.Left, subRoot) ||
		isSubtree(root.Right, subRoot)
}

// isSameTree 判断A与B两棵树相同
func isSameTree(a *TreeNode, b *TreeNode) bool {
	if a == nil && b == nil {
		return true
	}
	return a != nil && b != nil &&
		a.Val == b.Val &&
		isSameTree(a.Left, b.Left) &&
		isSameTree(a.Right, b.Right)
}
